
%Before going into the details of mapping variables as defined by the
% constraints that have been discussed above to structured queries, we 
%like to remind the reader of the the actual target of this operation:
% generating a well defined model describing structured queries (not necessarily the query
% string that can be executed on the data warehouse).
For most of the cases like the example given in
figure~\ref{fig:running-example}, a structured query contains a \emph{data
source},
%(i.e. data warehouse), 
a set of \emph{dimensions} and \emph{measures},
a set of \emph{filters} and an optional set of result modifiers, e.g.
\emph{ordering} or \emph{truncation} expressions. 
%There a more complex cases,
%where for instance the measure itself could be a computation based on other
%measures. However, for 
For the example from figure~\ref{fig:running-example}, a
stuctured query could be represented as follows:
%
%$
\begin{small}
\begin{equation*}
Q_1=\left[
\begin{array}{lcl}
\textnormal{data source} & = & \textnormal{Resorts}\\
\textnormal{dimensions} & = & \{\textnormal{Customer}\}\\
\textnormal{measures} & = & \{\textnormal{Revenue}\}\\
\textnormal{filters} & = &
\left\{
\begin{array}{lcl}
\textnormal{City} & = & \textnormal{`Palo
Alto'},\\
\textnormal{Age} & \geq & 20,\\
\textnormal{Age} & \leq & 30
\end{array}
\right\}
\\
\textnormal{truncation} & = &
\{(\textnormal{Revenue},\downarrow,5)\}
\end{array}
\right]
\end{equation*}
\end{small}
%$
%
In there, curly brackets represent a set of objects, which might have
a complex structure (e.g. for filters, which consist of a measure 
or dimension, an operator and a value). For truncations we use 
a triple consisting of the dimnesion or measure on which the 
ordering is applied, the ordering direction (ascending $\uparrow,$ or
descending $\downarrow$) and the number of items.
%
Another intepretation for the user's question
%(since it does not contain a measure) 
would be $Q_2$, which is similar to $Q_1$ except 
the proposed measure:  
%
%$
\begin{small}
\begin{equation*}
Q_2=\left[
\begin{array}{lcl}
\ldots\\
\textnormal{measures} & = & \{\textnormal{Margin}\}\\
\ldots\\
\textnormal{truncation} & = &
\{\textnormal{Margin},\downarrow,5)\}
\end{array}
\right]
\end{equation*}
\end{small}
%$
%
Since the reprentation shown above captures only a fraction of the 
potential queries, we use 
%again 
RDF to capture the 
structure and semantics of the structured query which is than serialized
to an executable query in a subsequent step.
%
As discussed earlier, we define in the left part of
figure~\ref{fig:structural-constraints} how to derive potential interpretations
(i.e. variables and the constraints between them) using a \textsc{SparQL}
{\footnotesize\verb|WHERE|} clause.
Now we need to define the basic structure of a query (in RDF)
and how to map variables into this model using a \textsc{SparQL} {\footnotesize 
\verb|CONSTRUCT|} clause (illustrated in the right 
part of figure~\ref{fig:structural-constraints}). In this way, we separate the
pattern matching, which can be quiet complex, from the actual mapping problem
%(which can be complex as well) 
and ensure a fine-grained  flexible control on how to generate structured queries. 
  
%As mentioned before, we do not map resource variables (such as a dimension), 
%but only literal variables into the query model to ensure the reusability 
%of the query model for other domains or use cases. The query model
%is therefore defined by its own RDF schema. 

%Graphs containing all possible interpretations of the user's question are generated at runtime.

%The schema of our query model is quiet complex and
%cannot be discussed here in full detail due to space constraints. However, 
%We show 
Some of the most important concepts of our query model are illustrated in
figure~\ref{fig:structural-constraints}. On the top, stands the root node
\yellownode{B} defining a structured query. 
%(`B' in figure~\ref{fig:structural-constraints}).
Below, 
%we show with 
dashed lines represent 
%the 
parts that are 
%defined to be 
optional in the left side.
% of figure~\ref{fig:structural-constraints}. 
These parts of the {\footnotesize 
 \verb|CONSTRUCT|} clause are only triggered if the 
respective variables are in the result of the {\footnotesize \verb|WHERE|} 
clause, making it easy to describe alternative
mappings for different situations as described in the \emph{parse graph}.
%
Besides of the actual query semantics, we attach some metadata nodes to the 
query node such as the \emph{data source} \lightrednode{DS}. 
%(`DS' in figure~\ref{fig:structural-constraints}).
It is 
%in turn 
bound to the variable `?w' representing the actual data warehouse
%on that 
upon which the generated query shall be executed. 
%Other important concepts are: 
Additional nodes are dedicated to:
\emph{projection items} \lightyellownode{PI}, capturing all projections 
that are part of the final structured query; \emph{filter items}
\lightyellownode{FI}, expressing selections on a certain measure or
dimension and \emph{truncation and ordering} clauses
\lightyellownode{TO}.
%We will detail 
The underlying structures are detailed in the following.

\textbf{Projections} The most important part of the actual query are
projections, which in our use-case consists at least of one measure and
dimension.
%However, an arbitrary number of measures and up to two dimensions are supported
%in the underlying real-world use case (defined as optional in the
%{\footnotesize \verb|WHERE|} clause).
%The limitations to two dimensions is due to the requirement to generate
%meaningfull charts as mentioned in section~\ref{sec:problem}.
% 
To give a glimpse on our full query model and further detail the example, 
we define different kinds of expressions (via a common anchestor
RDF type) where we depict here the subclasses \emph{measure expression}
\lightyellownode{ME} and \emph{dimensions expression}
\lightyellownode{DE}.
These nodes capture common metadata (not shown here), such as navigation paths
(e.g. for drill-down operations) or confidence scores and refer 
%in addition 
to the actual object that defines the projection, here the \emph{measure
reference} \lightyellownode{MR} and \emph{dimension reference}
\lightyellownode{DR}.
%These references
They are in our case the labels of recognized objects.
% measures as depicted in the left of figure~\ref{fig:structural-constraints}
% (`?mL1' and `?dL1'). Again, we like to point out that we 
%do not 
%need to 
It does not matter whether we use the recognized dimensions and measures
(derived from `m1' or `d1') or the suggested ones (derived from `m2' or `d4')
in the final query since we defined in the {\footnotesize\verb|WHERE|} clause
that suggestions are only made if no user input is available.
%
%Note that 
We plan to include more complex artifacts such as subnodes of the 
\emph{expression} anchestor node to support for instance computed measures.
%(e.g. for ad-hoc computation derived from questions containing for instance
%`relative margin' or `margin divided by revenue').    

\textbf{Truncation and Ordering} 
%One of the first nodes in the left of figure~\ref{fig:structural-constraints}
The node \lightyellownode{TO} in figure~\ref{fig:structural-constraints} stands
for \emph{Truncation and Ordering}.
It represents {\footnotesize \verb|ORDER BY|} and {\footnotesize \verb|LIMIT|}
clauses of a structured query or of a certain sub-select within such a query.
Thus, several nodes \lightyellownode{TO} can occur as sub-node of a query
node. If the variable `?nb' is not bound by the `TopK' pattern, the default value as described in
section~\ref{additional-variables} will be used and a single {\footnotesize
\verb|LIMIT|} will be generated. The `Sorting Expression' \lightyellownode{SE}
representing an {\footnotesize \verb|ORDER BY|} is not being generated in that
case because the variable `?ord' is unbound.
%
If the user entered a question starting with `Top\ldots' both variables 
`?nb' and `?ord' would be bound and we would suggest an artifact to apply the
ordering (unless the user entered `order by \ldots', which is parsed by a
dedicated pattern). Since \emph{top-$k$} questions usualy relate to a
particular measure (even if the query would be `top 5 cities'), we 
 can safely apply the order to the recognized or
 suggested measure by simply relating 
 the node for the `Sorting Expression' \lightyellownode{SE} to 
 the one for the measure \lightyellownode{MR}. Note that in any case
 %(also if the user mentioned several measures) 
every possible interpretation with respect to the {\footnotesize \verb|ORDER BY|} assigment would be generated.

\textbf{Filters:} \emph{Filter expressions} depicted as \lightyellownode{FE}
%in figure~\ref{fig:structural-constraints} 
represent a set of members 
%(i.e. dimension values) 
or numerical values in the case of measures 
%that shall
to be used to filter the
actual result.
From a data model perspective, filter expressions capture the metadata's
object (either dimension or measure) on which the restriction is applied and a
set or range of values that defines the actual restriction.
More complex filter expressions can be defined as well (e.g. containing
a sub-query).
%
In our example, we show only examples for \emph{member sets}
\lightyellownode{MS} containing a single member which is represented by a
\emph{value reference} \lightyellownode{VR}. In the first case,
% shows the situation where 
a member was directly recognized in the user's question. The variable `?dL2'
originating from the dimension `?d2' is directly assigned to the \emph{member
set} and a node for the \emph{value reference} \lightyellownode{VR} is generated
with a property for the actual value (i.e. `?vL1').
%Note that 
%It is straightforward to assign multiple matched members since
% references for not-bound variables will not be generated. 
%Another interesting aspect here is that 
Note that we do not need to care whether the respective dimensions will be
considered in the projections since this can be handled by constraints 
%as defined 
(see left part of figure~\ref{fig:structural-constraints}).
%
The second example 
%that we show here is the one for
handles personalization (e.g. 
%to handle for instance 
``my city'') and uses a filter leveraging the user profile.
It works similarly as the one for matched members except that 
%we define for 
the \emph{value reference} \lightyellownode{VR} 
%to
relates to the label of the object in the user profile that cares a similar
value as one of the members of a certain dimension (e.g. `Palo Alto' for the
dimension `City'). 
%Again we see that complex mappings like the one for
%personalization can be implemented easily.  
%
Range queries are conceptually similar to the ones containing a \emph{member
set}, no matter whether they are applied on dimensions or measures. 
The only difference is that a natural language pattern is used for 
detecting numeric or date range 
expressions in the user's question to define variables and that there are two 
\emph{value references} defining the 
%upper and lower bound 
bounds of the 
actual \emph{filter expression}.  

As result of the mapping step, we get an RDF graph containing all potential
interpretations (structured queries) of the user's question. Since the query 
model as such reflects the features of the underlying query language $L$ (e.g. 
projections and different types of selections) it is straightforward to 
serialize this model to an actual \emph{string} that can be executed on a data 
source. The constraints defined in previous sections ensure on the one hand 
how to treat different match situations and on the other hand 
that the generated queries are valid.
%(i.e. return a result). 
The great advantage of this approach
is that complex constraints can be defined in a declarative way and that they are
to some extend separated from the mapping problem, making the implementation
much %more easy
easier in presence of complex requirements. 
%What remains is to score
The generated structured queries must then be scored
% in order 
to provide a usefull ranking of results 
%to the end-user
and to define an order
according to which the computed queries are eventually executed.




 
 
 







% The whole structure (or ``parse tree'') that has been generated
% must then be mapped to a (database) structured query.
% The challenge here, is to generate a valid database query that captures the
% intention of the user.
% The question~\ref{fig:running-example} is mapped to internal representations
% of the multidimensional queries represented below:
% \begin{equation*}
% \begin{small}
% Q_1=\left[
% \begin{array}{lcl}
% \textnormal{data model} & = & \textnormal{Club}\\
% \textnormal{dimensions} & = & \{[\textnormal{Customer}]\}\\
% \textnormal{measures} & = & \{(\textnormal{Revenue})\}\\
% \textnormal{filters} & = &
% \left\{
% \begin{array}{lcl}
% [\textnormal{City}] & = & \textnormal{`Palo
% Alto'},\\
% \left[\textnormal{Age}\right] & \geq & 20,\\
% \left[\textnormal{Age}\right] & \leq & 30
% \end{array}
% \right\}
% \\
% \textnormal{orderings} & = & (\textnormal{Customer},\textnormal{Revenue})\\
% \textnormal{truncation} & = &
% \{((\textnormal{Customer},\textnormal{Revenue}),\downarrow,5)\}
% \end{array}
% \right]
% \end{small}
% %\label{eq:internal-query-1}
% \end{equation*}
% and
% \begin{equation*}
% \begin{small}
% Q_2=\left[
% \begin{array}{lcl}
% \textnormal{data model} & = & \textnormal{Club}\\
% \textnormal{dimensions} & = & \{[\textnormal{Customer}]\}\\
% \textnormal{measures} & = & \{(\textnormal{Margin})\}\\
% \textnormal{filters} & = &
% \left\{
% \begin{array}{lcl}
% [\textnormal{City}] & = & \textnormal{`Palo
% Alto'},\\
% \left[\textnormal{Age}\right] & \geq & 20,\\
% \left[\textnormal{Age}\right] & \leq & 30
% \end{array}
% \right\}
% \\
% \textnormal{ordering} & = & \{[\textnormal{Customer}].(\textnormal{Margin})\}\\
% \textnormal{truncation} & = &
% \{([\textnormal{Customer}],(\textnormal{Margin}),\downarrow,5)\}
% \end{array}
% \right]
% \end{small}
% %\label{eq:internal-query-2}
% \end{equation*}
% 
% The internal queries $Q_1$ and $Q_2$ represent the semantics captured by the
% structured (parse tree).
% There are two internal queries, because the constraints concerning the measures
% simply state that it must be an entity compatible with the other entities
% (i.e. [Customer], [City] and [Age]).
% The arrow ($\downarrow$) in the truncation clause of the conceptual queries
% stands for the descending order (here we consider the natural order $<$,
% and measures' domain values are supposed to be in $\mathbb{R}$).